// Created by WXX on 2021/8/30 10:47
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：68 ms, 在所有 C++ 提交中击败了93.92%的用户
 * 内存消耗：39.2 MB, 在所有 C++ 提交中击败了78.98%的用户
 */
class Solution {
public:
    vector<int> s;

    Solution(vector<int>& w) {
        s = w;
        for (int i = 1; i < w.size(); i++) s[i] += s[i - 1];
    }

    int pickIndex() {
        int x = rand() % s.back() + 1;  // 生成[1, s.back()]中的随机整数
        return lower_bound(s.begin(), s.end(), x) - s.begin();
    }
};

int main() {

    vector<int> w = {1, 2, 3};
    Solution *t = new Solution(w);
    for (int i = 0; i < 100; i++)
        cout << t->pickIndex() << endl;

    return 0;
}
